/**
 * @作者 zxy
 * @时间 2023-04-23 12:56
 * @说明 示例 1：
 * 输入：satisfaction = [-1,-8,0,5,-9]
 * 输出：14
 * 解释：去掉第二道和最后一道菜，最大的喜爱时间系数和为 (-1*1 + 0*2 + 5*3 = 14) 。每道菜都需要花费 1 单位时间完成。
 * 示例 2：
 * 输入：satisfaction = [4,3,2]
 * 输出：20
 * 解释：按照原来顺序相反的时间做菜 (2*1 + 3*2 + 4*3 = 20)
 * 示例 3：
 * 输入：satisfaction = [-1,-4,-5]
 * 输出：0
 * 解释：大家都不喜欢这些菜，所以不做任何菜可以获得最大的喜爱时间系数。
 */
public class Solution {
    public static void main(String[] args) {
        new Solution().maxSatisfaction(new int[]{
                233, -564, -853, -640, 947, -985, 470, -243, 971, -221, 445, 556, 44, 259, 376, -589, 814, -318, -82, -320, -491, -152, 492, -854, 146, -924, -781, -229, -526, -138, 257, -20, -991, -493, 901, -128, -855, -362, 767, -364, 976, -30, -77, 319, 797, 12, -767, -965, -139, 179, 481, -204, 108, 729, -854, -838, -863, -527, -902, -141, 975, -842, 970, 952, -714, 719, -412, 472, -698, 979, 413, -126, 737, 897, 132, -255, 484, -316, -617, 630, 153, -635, -89, 992, -716, 640, 874, -27, -26, 320, -969, -810, 383, -501, -325, 901, -719, 111, -286, -204, -156, -777, 419, 288, -975, -737, 684, -289, -461, -307, 729, -665, 250, 139, -76, -250, -439, 827, -800, 920, -991, -81, 624, -868, 165, 126, 236, -575, -995, -635, -77, 745, 263, -329, -42, 100, -93, 751, 870, -977, 546, -851, -785, -120, -395, -599, 591, 404, 478, 123, 393, -513, 368, 26, -753, -631, 944, -989, 917, -792, 653, -74, 248, 549, -730, 648, 41, 200, 636, -381, -946, -812, -505, 768, -715, -675, 105, 843, 238, 418, 791, 21, -796, 170, -334, 374, -659, 302, -669, -256, -645, 545, 924, -653, 616, 381, -453, -580, 322, -142, 367, -361, 841, 210, 38, -876, 127, 599, -104, 203, -246, 971, -80, -481, -146, 202, -148, 359, 71, -251, -941, 559, -315, -952, 894, -921, 977, -486, 857, -288, 539, 64, 87, -160, -279, -441, -195, 766, 647, 77, -877, 83, -215, 540, 845, 699, 533, 330, 392, 696, -55, 45, 397, 255, -498, 966, 70, -486, 501, 48, 109, 32, -619, -625, 445, -82, -699, 445, -862, -605, 798, 518, 757, 515, 533, -819, 138, -254, 110, 923, 430, 664, -364, -3, 983, 149, 792, -122, -391, -275, 771, -701, -45, 953, 50, -601, 840, 927, 535, -84, -281, 671, -931, -424, -797, -447, -525, 227, -725, -477, -12, 72, -99, -162, 232, 260, 849, 55, -995, -450, -253, -464, 177, 107, 211, 788, 865, -600, -950, -854, -617, 407, -783, -472, 806, 103, -10, 369, 368, -235, -100, -910, -435, 900, -606, 12, -232, 289, -101, -380, -147, 219, 790, 922, 497, 457, 23, -916, -621, -943, -256, 787, 492, 191, -61, -626, 863, -549, 573, 492, -192, -760, 741, -100, 795, 620, -297, -935, -342, -396, -42, 154, -358, -694, 662, -731, 815, 350, -205, 751, 781, -91, -170, 484, -861, 576, 136, -408, -300, 436, -405, -228, 195, 49, 922, 8, 348, 400, 314, -723, 952, 374, -583, 6, -137, 356, -739, -865, 639, -796, 538, 123, -187, 231, 154, -814, -325, -352, 559, 202, 553, 401, -873, 255, -511, 204, 14, 765, 267
        });
    }

    /**
     * 执行用时：1 ms , 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗： 40.7 MB, 在所有 Java 提交中击败了8.21%的用户
     * @param satisfaction
     * @return
     */
    public int maxSatisfaction(int[] satisfaction) {
        int[] rec = new int[2001];
        for (int value : satisfaction) {
            rec[value + 1000]++;
        }
        int max = 0;
        int add = 0;
        for (int i = rec.length - 1; i >= 0; i--) {
            while (rec[i] != 0) {
                rec[i]--;
                add += (i - 1000);
                if (add < 0) break;
                max += add;
            }
        }
        return max;
    }
}
